package com.ssh;

import org.junit.Test;

public class NumIslands_200 {
	private int m, n;
	private int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	public int numIslands(char[][] grid) {
		if (grid == null || grid.length == 0) {
			return 0;
		}
		n = grid.length;
		m = grid[0].length;
		int sum = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				sum += max(grid, i, j);
			}
		}
		return sum;
    }
	
	private int max(char[][] grid, int x, int y) {
		if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '0') {
			return 0;
		}
		grid[x][y] = '0';
		for (int[] d : dir) {
			max(grid, x + d[0], y + d[1]);
		}
		return 1;
	}
	
	@Test
	public void test() {
		char[][] a = 
				{{'1','1','0','0','0'},
				 {'1','1','0','0','0'},
				 {'0','0','1','0','0'},
				 {'0','0','0','1','1'}
				 };
		System.out.println(numIslands(a));
	}
}
